package leetcode.editor.cn;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

/**
题目名字---:寻找重复数
题目编号---:287	
解题时间---:2021-09-24 23:25:23
*/

public class FindTheDuplicateNumber{
    public static void main(String[] args) {
        Solution solution = new FindTheDuplicateNumber().new Solution();    
    }

    /**
     * 1.暴力法求解--双重for循环--超时
     * @param nums
     * @return
     */
    public int findDuplicate1(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (nums[i]==nums[j]) {
                    return nums[i];
                }
            }
        }
        return 0;
    }

    /**
     * 2.HashMap保存 --空间复杂度O(n)
     *   时间复杂度--O(n)
     * @param nums
     * @return
     */
    public int findDuplicate2(int[] nums) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (hashMap.containsKey(nums[i])) {
                return nums[i];
            }
            hashMap.put(nums[i],nums[i]);
        }
        return 0;
    }

    /**
     * 使用HashSet保存
     * @param nums
     * @return
     */
    public int findDuplicate3(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (hashSet.contains(nums[i])) {
              return nums[i];
            }
            hashSet.add(nums[i]);
        }
        return 0;
    }

    /**
     * 先排序,便利索引
     * 空间复杂度O(1)  --内存使用 回减少
     * 时间复杂度O(n*n)
     * @param nums
     * @return
     */
    public int findDuplicate4(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]==nums[i+1]) {
                return nums[i];
            }
        }
        return 0;
    }
    
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]==nums[i-1]) {
                return nums[i];
            }
        }
        return 0;
    }
}
//leetcode submit region end(Prohibit modification and deletion)


}